package com.fmm.medium;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class FinishCourseTable {

    /**
     * @param p 课程依赖关系
     * @return 是否可以完成课程
     * */
    public static boolean canFinishCourseTable(int[][] p) {
        Map<Integer, Set<Integer>> map = new HashMap();
        for (int i = 0; i < p.length; i++) {
            int from = p[i][0];
            int to = p[i][1];
            map.computeIfAbsent(from, k -> new HashSet()).add(to);
        }
        return !hasCycle(map, new HashSet(), 0, new HashMap());
    }


    private static boolean hasCycle(
            Map<Integer, Set<Integer>> map,
            Set<Integer> visited,
            int node,
            Map<Integer, Boolean> cache) {

        if (cache.containsKey(node)) { // 缓存中有，则直接返回
            return cache.get(node);
        }

        Set<Integer> children = map.get(node); // 获取当前节点的子节点
        if (children == null) { // 自己是叶子节点，没有环
            cache.put(node, false); // 缓存当前 node 节点没有环
            return false;
        }

        // 遍历子节点，当所有子节点都没有环时，自己也算没有环
        for (Integer child : children) {
            if (visited.contains(child)) { //  如果子节点被访问过，则说明有环
                cache.put(node, true); // 缓存当前 node 节点有环
                return true;
            }
            visited.add(child); //  标记子节点被访问过
            if (hasCycle(map, visited, child, cache)) { // 递归判断子节点的子节点，如果有环，则返回true
                cache.put(node, true); // 缓存当前 node 节点有环
                return true;
            } else { // 否则，将子节点从已访问的节点中移除
                visited.remove(child);
            }
        }
        cache.put(node, false); // 缓存当前 node 节点没有环
        return false;
    }

    public static void main(String[] args) {
        int[][] p = new int[][]{
                {0, 1},
                {1, 0}
        };
        System.out.println(canFinishCourseTable(p));
    }
}
